«
»

Finding the greatest subtree of a binary tree

March 26, 2012, 9:35 pm

Another rough and ready algorithm. Finding the greatest subtree in a binary tree…

Things to remember, values in the tree can be negative so it’s not just the root (sigh).

This implementation is very inefficient. Caching sum in the node makes the efficiency reasonable I believe. But the problem is essentially recursive? Should do some googling to see if there is a better solution.

#include <iostream>

using namespace std;

class Node {

public:

  Node () : left(NULL), right(NULL) {}

  int value;
  int sum;

  Node *left;
  Node *right;

  int getsum() {
    sum = 0;
    if((left == NULL) && (right == NULL)) return value;

    if(left != NULL)  sum += left->getsum();
    if(right != NULL) sum += right->getsum();
    sum += value;

    return sum;
  }
};


Node *greatestsubtree(Node *current,Node *max) {

  if(current == NULL) return max;

  int mval = current->getsum();

  if(mval > max->getsum()) max = current;

  Node *l = greatestsubtree(current->left,max);
  Node *r = greatestsubtree(current->right,max);
  if(l->getsum() > max->getsum()) max = l;
  if(r->getsum() > max->getsum()) max = r;

  return max;
}

int main() {

  Node *root  = new Node();
  root->left  = new Node();
  root->right = new Node();
  root->value = 10;

  root->left->value = -10;
  root->right->value = 5;

  root->left->left = new Node();
  root->left->left->value = 100;
  root->left->right = new Node();
  root->left->right->value = 0;

  root->right->left = new Node();
  root->right->left->value = -8;

  cout << root << endl;
  cout << greatestsubtree(root,root)->getsum();
}

Version with caching…


#include <iostream>

using namespace std;

class Node {

public:

  Node () : left(NULL), right(NULL),sumcache(false) {}

  int value;
  int sum;
  bool sumcache;
  
  Node *left;
  Node *right;
  
  int getsum() {

    if(sumcache) return sum;

    sum = 0;
    if((left == NULL) && (right == NULL)) return value;
    
    if(left != NULL)  sum += left->getsum();
    if(right != NULL) sum += right->getsum();
    sum += value;
    
    sumcache = true;
    return sum;
  }
};


Node *greatestsubtree(Node *current,Node *max) {

  if(current == NULL) return max;

  int mval = current->getsum();
  
  if(mval > max->getsum()) max = current;

  Node *l = greatestsubtree(current->left,max);
  Node *r = greatestsubtree(current->right,max);
  if(l->getsum() > max->getsum()) max = l;
  if(r->getsum() > max->getsum()) max = r;

  return max;
}

int main() {

  Node *root  = new Node();
  root->left  = new Node();
  root->right = new Node();
  root->value = 10;

  root->left->value = -10;
  root->right->value = 5;

  root->left->left = new Node();
  root->left->left->value = 100;
  root->left->right = new Node();
  root->left->right->value = 0;

  root->right->left = new Node();
  root->right->left->value = -8;

  cout << root << endl;
  cout << greatestsubtree(root,root)->getsum();
}
Category: Uncategorized  |  Comment (RSS)  |  Trackback